package com.cc.od.enhanc;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
@description:
                    题目描述
                    C语言中的strstr函数用于在字符串haystack中查找第一次出现字符串needle的位置，如果未找到则返回NULL。现在要求实现一个增强的strstr函数，该函数可以使用带可选段的字符串来模糊查询。可选段使用[]标识，表示该位置可以是可选段中的任意一个字符即可满足匹配条件。例如，"a[bc]"可以匹配"ab"或"ac"。

                    输入描述
                    输入包含两个字符串，分别是源字符串和目标字符串，以空格分隔。

                    输出描述
                    输出一个整数，表示匹配子字符串在源字符串中的起始位置（从0开始计数）。如果没有匹配，则输出-1。

                    注意事项
                    源字符串中不包含[]。
                    目标字符串中的[]成对出现，且不会嵌套。
                    输入的字符串长度在[1,100]之间。
                    解题思路
                    解析目标字符串：将目标字符串解析为模式数组，其中普通字符直接保存，可选字符用集合（如Python中的set）表示。
                    在源字符串中查找匹配：遍历源字符串，对每个位置尝试匹配模式数组。如果完全匹配，返回当前位置；如果不匹配，继续下一个位置。
                    返回结果：如果遍历完源字符串仍未找到匹配，返回-1。
@ClassName EnhancedStrStr
@author chen
@create 2024-09-29 15:37
@Version 1.0
*/
public class EnhancedStrStr {


    public static void main(String[] args) {
        String haystack = "abc";
        String needle = "b[cd]";
        int i = enhancedStrStr(haystack, needle);
        System.out.println(i);
    }

    public static int enhancedStrStr(String haystack, String needle)
    {
        // 将 'needle' 字符串解析为字符和字符集列表
        List<Object> pattern = parsePattern(needle);
        // 在 'haystack' 中查找匹配项
        for (int i = 0; i <= haystack.length() - patternLength(pattern); i++)
        {
            if (matchesPattern(haystack, i, pattern))
            {
                // 如果找到匹配项，返回当前索引
                return i;
            }
        }
        return 0;
    }

    private static boolean matchesPattern(String haystack, int startIndex, List<Object> pattern)
    {
        for (int i = 0; i < pattern.size(); i++)
        {
            Object p = pattern.get(i);
            // 检查剩余的字符串长度是否足以完成模式的匹配
            if (startIndex + i >= haystack.length())
            {
                return false; // haystack剩余长度不足以匹配整个模式
            }
            char haystackChar = haystack.charAt(startIndex + i);
            // 根据模式元素的类型，进行字符精确匹配或选项集匹配
            if(p instanceof Character)
            {
                // 如果模式元素是字符类型，比较字符是否完全相同
                if (haystackChar != (char) p)
                {
                    return false;
                }
            }
            else if (p instanceof Set)
            {
                Set<Character> options = (Set<Character>) p;
                // 如果模式元素是选项集类型，检查字符是否属于选项集
                if (!options.contains(haystackChar))
                {
                    return false;
                }
            }
        }
        return true;
    }

    private static int patternLength(List<Object> pattern)
    {
        // 初始化长度计数器
        int length = 0;
        // 遍历匹配模式中的每个元素
        for (Object p : pattern)
        {
            // 如果元素是字符，长度增加1
            if(p instanceof Character)
            {
                length ++;
            }
            else if(p instanceof Set)
            {
                // 如果元素是字符集，也视为一个整体，长度增加1
                // 字符集只占用一个位置，但匹配时可以是集合中的任何一个字符
                length ++;
            }
        }
        return length;
    }

    private static List<Object> parsePattern(String needle)
    {
        List<Object> pattern = new ArrayList<>();
        StringBuilder currentOption = null;

        // 遍历输入字符串中的每个字符
        for (char c : needle.toCharArray())
        {
            // 处理方括号内选项的开始
            if (c == '[')
            {
                // 如果当前已有未处理的选项，说明嵌套使用了方括号，抛出异常
                if (currentOption != null)
                {
                    throw new IllegalArgumentException("Invalid needle string: Nested [] not allowed");
                }
                // 开始新的选项构建
                currentOption = new StringBuilder();
            }
            // 处理方括号内选项的结束
            else if (c == ']')
            {
                // 如果当前没有正在构建的选项，说明方括号配对不正确，抛出异常
                if (currentOption == null) {
                    throw new IllegalArgumentException("Invalid needle string: Unmatched ]");
                }
                // 将当前选项字符串转换为字符集合并添加到模式中
                Set<Character> options = new HashSet<>();
                for (char optionChar : currentOption.toString().toCharArray())
                {
                    options.add(optionChar);
                }
                pattern.add(options);
                currentOption = null;
            }
            // 处理普通字符或当前选项内的字符
            else
            {
                // 根据当前选项构建状态决定是追加到选项中还是作为普通字符添加到模式中
                if (currentOption != null)
                {
                    currentOption.append(c);
                }
                else
                {
                    pattern.add(c);
                }
            }
        }
        // 检查是否有未闭合的方括号，如果有，抛出异常
        if (currentOption != null)
        {
            throw new IllegalArgumentException("Invalid needle string: Unclosed []");
        }
        return pattern;
    }

}
